package cc.rico.algorithm;

/**
 * @Author: Dell
 * @Date: 2018/12/6
 * @Description:
 */
public class HeapSort {


    public static void main(String[] args) {
        int[] items = new int[9];

        int current = 0;
        insert(items, 12, current);

        current++;
        insert(items, 10, current);

        current++;
        insert(items, 15, current);
        sortUp(items, current);
        System.out.println("============================================");
        PrintUtil.printArray(items);

        current++;
        insert(items, 21, current);
        sortUp(items, current);
        System.out.println("============================================");
        PrintUtil.printArray(items);

        current++;
        insert(items, 41, current);
        sortUp(items, current);
        System.out.println("============================================");
        PrintUtil.printArray(items);

        current++;
        insert(items, 1, current);
        sortUp(items, current);
        System.out.println("============================================");
        PrintUtil.printArray(items);

        //current++;

        items = delete(items, current);
        System.out.println("=====================sortDown=======================");
        PrintUtil.printArray(items);

        sortDown(items, 0 , current);
        System.out.println("=====================sortDown=======================");
        PrintUtil.printArray(items);

    }

    private static void insert(int[] items, int value, int current) {
        if(current == 0) {
            items[0] = value;
            return;
        }

        if(current == 1) {
            if(value > items[0]) {
                int temp = items[0];
                items[0] = value;
                items[current] = temp;

            } else {
                items[current] = value;
            }

            return;
        }

        if(current == 2) {
            if(value > items[0]) {
                int temp = items[0];
                items[0] = value;
                items[current] = temp;

            } else {
                items[current] = value;
            }

            return;
        }

        items[current] = value;
    }

    private static void sortUp(int[] items, int current) {
        int p = parent(current);

        while (p >= 0) {
            int pValue = items[p];
            int currentValue = items[current];

            if(currentValue > pValue) {
                items[p] = currentValue;
                items[current] = pValue;
                current = p;

            } else {
                break;
            }

            if(current == 0) {
                break;
            }

            p = parent(p);
        }
    }

    private static int[] delete(int[] items, int current) {
        int[] tempItems = new int[9];
        tempItems[0] = items[current];

        for(int i=1; i<current; i++) {
            tempItems[i] = items[i];
        }
        return tempItems;
    }

    private static void sortDown(int[] items, int p, int current) {
        //int p = 0;
        int maxIndex = items.length - 1;

        int left = left(p);
        int right = right(p);

        while (left < maxIndex) {

            if(items[left] > items[right]) {
                int temp = items[p];
                items[p] = items[left];
                items[left] = temp;
                p = left;

            } else {
                int temp = items[p];
                items[p] = items[right];
                items[right] = temp;
                p = right;
            }

            left = left(p);
            right = right(p);
        }
    }

    private static int parent(int current) {
        if(current == 0) {
            return 0;
        }

        return (int) Math.floor((current-1)/2);
    }

    private static int left(int current) {
        if(current == 0) {
            return 1;
        }

        return current*2+1;
    }

    private static int right(int current) {
        if(current == 0) {
            return 2;
        }

        return current*2+2;
    }


}
